package com.example.demo.tool;

import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class RepetitionRate {

    private static final Pattern PATTERN = Pattern.compile("\\s");

    /**
     * 利用LCS算法计算重复率
     *
     * @param x
     * @param y
     * @return
     */
    //
    public static double computeByLCS(String x, String y) {
        // 格式化，变成字符串无空格无回车等
        x = replaceBlank(x);
        y = replaceBlank(y);
        int xLen = x.length();
        int yLen = y.length();
        // 构造二维数组记录子问题x[i]和y[i]的LCS的长度
        int[][] opt = new int[xLen + 1][yLen + 1];
        // 动态规划计算所有子问题
        for (int i = xLen - 1; i >= 0; i--) {
            for (int j = yLen - 1; j >= 0; j--) {
                if (x.charAt(i) == y.charAt(j))
                    opt[i][j] = opt[i + 1][j + 1] + 1;
                else
                    opt[i][j] = Math.max(opt[i + 1][j], opt[i][j + 1]);
            }
        }
        int len = xLen <= yLen ? xLen : yLen;
        return 1.0 * opt[0][0] / len;

        // 输出最长公共子序列
//        int i = 0, j = 0;
//        while (i < xLen && j < yLen){
//            if (x.charAt(i) == y.charAt(j)){
//                System.out.print(x.charAt(i));
//                i++;
//                j++;
//            } else if (opt[i + 1][j] >= opt[i][j + 1])
//                i++;
//            else
//                j++;
//        }

    }

    /**
     * 替换字符串中的空格、制表符、回车符、换行符
     *
     * @param str
     * @return
     */
    private static String replaceBlank(String str) {
        String dest = "";
        if (str != null) {
            Matcher m = PATTERN.matcher(str);
            dest = m.replaceAll("");
        }
        return dest;
    }
}
